use std::iter::Filter;

const COINS: [u32; 8] = [100, 50, 30, 20, 10, 5, 2, 1];

struct Decomposer<Coins> {
    cash: u32,
    coins: Coins,
}

impl<Coins> Decomposer<Coins> {
    pub fn new(
        cash: u32,
    ) -> Decomposer<Filter<std::array::IntoIter<u32, 8>, impl FnMut(&u32) -> bool>> {
        Decomposer {
            cash,
            coins: COINS.into_iter().filter(move |&n| n <= cash),
        }
    }
}

impl<Coins: Iterator<Item = u32>> Iterator for Decomposer<Coins> {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        let coin = self.coins.next()?;
        let amount = self.cash / coin;
        self.cash %= coin;
        Some(amount)
    }
}

pub fn dp_rec_mc(amount: u32) -> u32 {
    Decomposer::<()>::new(amount).filter(|&n| n > 0).count() as u32
}
